#include <bits/stdc++.h>

using namespace std;

// 我们假设这个数据范围不爆int
vector<int> temp;
int merge_sort(vector<int> &array, int l, int r) {
    if (l >= r) return 0;
    int mid = l + ((r - l) >> 1), idx = 0, i = l, j = mid + 1;
    int cnt = merge_sort(array, l, mid) + merge_sort(array, mid + 1, r);
    while (i <= mid && j <= r) {
        if (array[i] <= array[j]) {
            temp[idx++] = array[i++];
            cnt += j - mid - 1;
        }
        else temp[idx++] = array[j++];
    }
    while (i <= mid) { temp[idx++] = array[i++]; cnt += j - mid - 1; }
    while (j <= r) temp[idx++] = array[j++];
    while (idx--) array[l + idx] = temp[idx];
    return cnt;
}
int count_ReversedPairs(vector<int> &array) {
    int len = array.size();
    temp.resize(len);
    return merge_sort(array, 0, len - 1);
}

int main() {
    /*
    (11,7)  (11,6)  (11,4)  (11,5)  (7,6)  (7,4)  (7,5)  (6,4)  (6,5)
    */
    vector<int>array{ 11, 7, 6, 4, 5 };
    cout << count_ReversedPairs(array) << endl;  // 9
    //system("pause");
    return 0;
}
